home *** CD-ROM | disk | FTP | other *** search
/ Java Programmer's Toolkit / Java Programmer's Toolkit.iso / applets / collectn / llmap.jav < prev    next >
Text File  |  1995-12-14  |  9KB  |  369 lines
  1. /*
  2.   File: LLMap.java
  3.  
  4.   Originally written by Doug Lea and released into the public domain. 
  5.   Thanks for the assistance and support of Sun Microsystems Labs, Agorics 
  6.   Inc, Loral, and everyone contributing, testing, and using this code.
  7.  
  8.   History:
  9.   Date     Who                What
  10.   24Sep95  dl@cs.oswego.edu   Create from collections.java  working file
  11.   13Oct95  dl                 Changed protection statuses
  12.   21Oct95  dl                 Fixed error in removeAt
  13.  
  14. */
  15.   
  16. package collections;
  17.  
  18. import java.util.Enumeration;
  19. import java.util.NoSuchElementException;
  20.  
  21. /**
  22.  *
  23.  *
  24.  * Linked lists of (key, element) pairs
  25.  * @author Doug Lea
  26.  * @version 0.93
  27.  *
  28.  * <P> For an introduction to this package see <A HREF="index.html"> Overview </A>.
  29. **/
  30.  
  31.  
  32. public class LLMap extends UpdatableMapImpl implements UpdatableMap {
  33.  
  34. // instance variables
  35.  
  36. /**
  37.  * The head of the list. Null if empty
  38. **/
  39.  
  40.   protected LLPair list_;
  41.  
  42. // constructors
  43.  
  44. /**
  45.  * Make an empty list
  46. **/
  47.  
  48.   public LLMap() { this(null, null, 0); }
  49.  
  50. /**
  51.  * Make an empty list with the supplied element screener
  52. **/
  53.  
  54.   public LLMap(Predicate screener) { this(screener, null, 0); }
  55.  
  56. /**
  57.  * Special version of constructor needed by clone()
  58. **/
  59.   protected LLMap(Predicate s, LLPair l, int c) { 
  60.     super(s); list_ = l;  count_ = c;
  61.   }
  62.  
  63. /**
  64.  * Make an independent copy of the list. Does not clone elements
  65. **/
  66.  
  67.   protected Object clone()  throws CloneNotSupportedException { 
  68.     if (list_ == null) return new LLMap(screener_, null, 0);
  69.     else return new LLMap(screener_, (LLPair)(list_.copyList()), count_);  
  70.   }
  71.  
  72.  
  73. // Collection methods
  74.  
  75. /**
  76.  * Implements collections.Collection.includes.
  77.  * Time complexity: O(n).
  78.  * @see collections.Collection#includes
  79. **/
  80.   public synchronized boolean includes(Object element) {
  81.     if (element == null || list_ == null) return false;
  82.     return list_.find(element) != null;
  83.   }
  84.  
  85. /**
  86.  * Implements collections.Collection.occurrencesOf.
  87.  * Time complexity: O(n).
  88.  * @see collections.Collection#occurrencesOf
  89. **/
  90.   public synchronized int occurrencesOf(Object element) {
  91.     if (element == null || list_ == null) return 0;
  92.     return list_.count(element);
  93.   }
  94.  
  95. /**
  96.  * Implements collections.Collection.elements.
  97.  * Time complexity: O(1).
  98.  * @see collections.Collection#elements
  99. **/
  100.   public synchronized CollectionEnumeration elements() { 
  101.     return new LLPairEnumeration(this, list_, false); 
  102.   }
  103.  
  104. // Map methods
  105.  
  106.  
  107. /**
  108.  * Implements collections.Map.includesKey.
  109.  * Time complexity: O(n).
  110.  * @see collections.Map#includesKey
  111. **/
  112.   public synchronized boolean  includesKey(Object key) {
  113.     if (key == null || list_ == null) return false;
  114.     return list_.findKey(key) != null;
  115.   }
  116.  
  117. /**
  118.  * Implements collections.Map.includesAt
  119.  * Time complexity: O(n).
  120.  * @see collections.Map#includesAt
  121. **/
  122.   public synchronized boolean includesAt(Object key, Object element) {
  123.     if (key == null || element == null || list_ == null) return false;
  124.     return list_.find(key, element) != null;
  125.   }
  126.  
  127. /**
  128.  * Implements collections.Map.keys.
  129.  * Time complexity: O(1).
  130.  * @see collections.Map#keys
  131. **/
  132.   public synchronized CollectionEnumeration keys() { 
  133.     return new LLPairEnumeration(this, list_, true); 
  134.   }
  135.  
  136. /**
  137.  * Implements collections.Map.at.
  138.  * Time complexity: O(n).
  139.  * @see collections.Map#at
  140. **/
  141.   public synchronized Object at(Object key) 
  142.   throws  NoSuchElementException {
  143.     checkKey(key);
  144.     if (list_ != null) {
  145.       LLPair p = list_.findKey(key);
  146.       if (p != null) return p.element();
  147.     }
  148.     throw new NoSuchElementException("no Key matching argument " + key);
  149.   }
  150.  
  151. /**
  152.  * Implements collections.Map.aKeyOf.
  153.  * Time complexity: O(n).
  154.  * @see collections.Map#aKeyOf
  155. **/
  156.   public synchronized Object aKeyOf(Object element) {
  157.     if (element == null || count_ == 0) return null;
  158.     LLPair p = ((LLPair)(list_.find(element)));
  159.     if (p != null)
  160.       return p.key();
  161.     else
  162.       return null;
  163.   }
  164.  
  165.  
  166. // UpdatableCollection methods
  167.  
  168. /**
  169.  * Implements collections.UpdatableCollection.clear.
  170.  * Time complexity: O(1).
  171.  * @see collections.UpdatableCollection#clear
  172. **/
  173.   public synchronized void clear() { 
  174.     list_ = null; 
  175.     setCount(0); 
  176.   }
  177.  
  178. /**
  179.  * Implements collections.UpdatableCollection.replaceOneOf
  180.  * Time complexity: O(n).
  181.  * @see collections.UpdatableCollection#replaceOneOf
  182. **/
  183.   public synchronized void replaceOneOf(Object oldElement, Object newElement)  
  184.   throws IllegalElementException { 
  185.     replace_(oldElement, newElement, false);
  186.   }
  187.  
  188. /**
  189.  * Implements collections.UpdatableCollection.replaceAllOf.
  190.  * Time complexity: O(n).
  191.  * @see collections.UpdatableCollection#replaceAllOf
  192. **/
  193.   public synchronized void replaceAllOf(Object oldElement, 
  194.                                                  Object newElement) 
  195.   throws IllegalElementException {
  196.     replace_(oldElement, newElement, true);
  197.   }
  198.  
  199. /**
  200.  * Implements collections.UpdatableCollection.exclude.
  201.  * Time complexity: O(n).
  202.  * @see collections.UpdatableCollection#exclude
  203. **/
  204.   public synchronized void exclude(Object element)  { 
  205.     remove_(element, true);
  206.   }
  207.  
  208. /**
  209.  * Implements collections.UpdatableCollection.removeOneOf.
  210.  * Time complexity: O(n).
  211.  * @see collections.UpdatableCollection#removeOneOf
  212. **/
  213.   public synchronized void removeOneOf(Object element)  { 
  214.     remove_(element, false);
  215.   }
  216.  
  217. /**
  218.  * Implements collections.UpdatableCollection.take.
  219.  * Time complexity: O(1).
  220.  * takes the first element on the list
  221.  * @see collections.UpdatableCollection#take
  222. **/
  223.   public synchronized Object take() 
  224.   throws NoSuchElementException {
  225.     if (list_ != null) {
  226.       Object v = list_.element();
  227.       list_ = (LLPair)(list_.next());
  228.       decCount();
  229.       return v;
  230.     }
  231.     checkIndex(0);
  232.     return null; // not reached
  233.   }
  234.  
  235.  
  236. // UpdatableMap methods
  237.  
  238. /**
  239.  * Implements collections.UpdatableMap.putAt.
  240.  * Time complexity: O(n).
  241.  * @see collections.UpdatableMap#putAt
  242. **/
  243.   public synchronized void putAt(Object key, Object element) {
  244.     checkKey(key);
  245.     checkElement(element);
  246.     if (list_ != null) {
  247.       LLPair p = list_.findKey(key);
  248.       if (p != null) {
  249.         if (!p.element().equals(element)) {
  250.           p.element(element);
  251.           incVersion();
  252.         }
  253.         return;
  254.       }
  255.     }
  256.     list_ = new LLPair(key, element, list_);
  257.     incCount();
  258.   }
  259.  
  260.  
  261. /**
  262.  * Implements collections.UpdatableMap.removeAt.
  263.  * Time complexity: O(n).
  264.  * @see collections.UpdatableMap#removeAt
  265. **/
  266.   public synchronized void  removeAt(Object key) {
  267.     if (key == null || list_ == null) return;
  268.     LLPair p = list_;
  269.     LLPair trail = p;
  270.     while (p != null) {
  271.       LLPair n = (LLPair)(p.next());
  272.       if (p.key().equals(key)) {
  273.         decCount();
  274.         if (p == list_) list_ = n;
  275.         else trail.unlinkNext();
  276.         return;
  277.       }
  278.       else {
  279.         trail = p;
  280.         p = n;
  281.       }
  282.     }
  283.   }
  284.  
  285. /**
  286.  * Implements collections.UpdatableMap.replaceElement.
  287.  * Time complexity: O(n).
  288.  * @see collections.UpdatableMap#replaceElement
  289. **/
  290.   public synchronized void replaceElement(Object key, Object oldElement, 
  291.                                           Object newElement)  
  292.   throws IllegalElementException { 
  293.     if (key == null || oldElement == null || list_ == null) return;
  294.     LLPair p = list_.find(key, oldElement);
  295.     if (p != null) {
  296.       checkElement(newElement);
  297.       p.element(newElement);
  298.       incVersion();
  299.     }
  300.   }
  301.  
  302.   private void remove_(Object element, boolean allOccurrences)  { 
  303.     if (element == null || count_ == 0) return;
  304.     LLPair p = list_;
  305.     LLPair trail = p;
  306.     while (p != null) {
  307.       LLPair n = (LLPair)(p.next());
  308.       if (p.element().equals(element)) {
  309.         decCount();
  310.         if (p == list_) { list_ = n; trail = n; }
  311.         else trail.next(n);
  312.         if (!allOccurrences || count_ == 0) return;
  313.         else p = n;
  314.       }
  315.       else {
  316.         trail = p;
  317.         p = n;
  318.       }
  319.     }
  320.   }
  321.  
  322. /**
  323.  * Helper for replace
  324. **/
  325.  
  326.   private void replace_(Object oldElement, Object newElement, 
  327.                           boolean allOccurrences)  
  328.   throws IllegalElementException { 
  329.     if (list_ == null || oldElement == null || oldElement.equals(newElement))
  330.       return;
  331.     LLCell p = list_.find(oldElement);
  332.     while (p != null) { 
  333.     checkElement(newElement);
  334.       p.element(newElement);
  335.       incVersion();
  336.       if (!allOccurrences) return;
  337.       p = p.find(oldElement);
  338.     }
  339.   }
  340.  
  341. // ImplementationCheckable methods
  342.  
  343. /**
  344.  * Implements collections.ImplementationCheckable.checkImplementation.
  345.  * @see collections.ImplementationCheckable#checkImplementation
  346. **/
  347.   public synchronized void checkImplementation() 
  348.   throws ImplementationError {
  349.  
  350.     super.checkImplementation();
  351.  
  352.     assert(((count_ == 0) == (list_ == null)));
  353.     assert((list_ == null || list_.length() == count_));
  354.  
  355.     for (LLPair p = list_; p != null; p = (LLPair)(p.next())) {
  356.       assert(canInclude(p.element()));
  357.       assert(canIncludeKey(p.key()));
  358.       assert(includesKey(p.key()));
  359.       assert(includes(p.element()));
  360.       assert(occurrencesOf(p.element()) >= 1);
  361.       assert(includesAt(p.key(), p.element()));
  362.     }
  363.  
  364.   }
  365.  
  366.  
  367. }
  368.  
  369.